package 最短路;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.HashMap;
import java.util.Map;

public class Floyd {

    static final int N = 210, INF = 9999;
    static int n, m, k, choose;
    static boolean isContinue = true;
    static int[][] adjacencyMatrix,temp;

    static HashMap<Integer, String> map = new HashMap<>();
    static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() throws Exception {
        in.nextToken();
        return (int) in.nval;
    }

    static String next() throws Exception {
        in.nextToken();
        return in.sval;
    }


    static void addCity() throws Exception {
        System.out.println("请输入要添加城市的数量");
        int cityNum = nextInt();
        while (cityNum-- > 0) {
            System.out.println("输入：城市编号 城市名");
            int number = nextInt();
            String cityName = next();
            if (map.containsKey(number)) {
                System.out.println("该城市已经存在，请添加其他城市");
            } else {
                map.put(number,cityName);
                n--;
            }
        }
    }


    static void inputModel() throws Exception {
        System.out.println("请选择表示方式：");
        System.out.println("1.方式一：点 点 边");
        System.out.println("2.方式二：直接输入邻接矩阵");
        int x = nextInt();
        switch (x) {
            case 1:
                System.out.println("请输入点，边的数量(即 n m)");
                n = nextInt();
                m = nextInt();
                adjacencyMatrix = new int[n+1][n+1];
                temp = new int[n+1][n+1];
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        if (i == j) {
                            adjacencyMatrix[i][j] = 0;
                            temp[i][j]  = 0;
                        } else {
                            adjacencyMatrix[i][j] = INF;
                            temp[i][j]  = INF;
                        }
                    }
                }
                while (m-- > 0) {
                    int a = nextInt();
                    int b = nextInt();
                    int c = nextInt();
                    if (!map.containsKey(a) && !map.containsKey(b)) {
                        if (!map.containsKey(a)) {
                            System.out.println("不存在" + a + "号城市，请重新输入或添加该城市");
                        } else if (!map.containsKey(b)) {
                            System.out.println("不存在" + b + "号城市，请重新输入或添加该城市");
                        } else {
                            System.out.println("不存在" + a + "和" + b + "号城市，请重新输入或添加该城市");
                        }
                        break;
                    }

                    adjacencyMatrix[a][b] = Math.min(adjacencyMatrix[a][b], c);
                    temp[a][b] = adjacencyMatrix[a][b];
                    adjacencyMatrix[b][a]  = adjacencyMatrix[a][b];
                }
                break;
            case 2:
                System.out.println("请输入n*n的邻接矩阵");
                n = nextInt();
                m = nextInt();
                adjacencyMatrix = new int[n+1][n+1];
                temp = new int[n+1][n+1];
                for (int i = 1; i <= n; i++) {
                    for (int j = 1; j <= n; j++) {
                        adjacencyMatrix[i][j] = nextInt();
                        temp[i][j]  = adjacencyMatrix[i][j];
                    }
                }
                break;
            default:
                System.out.println("输入错误，请重新输入");
        }
        floyd();
    }

    static void showInput(){
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    if (temp[i][j] > INF *2/3 ) {
                        System.out.println(map.get(i) + "到" + map.get(j) + "不能直接到达");
                    } else {
                        System.out.println(map.get(i) + "到" + map.get(j) + "的距离为" + temp[i][j] + "万公里");
                    }
                }

            }
        }


    }

    static void query() throws Exception {
        System.out.println("请输入查询数量");
        k = nextInt();
        while (k-- > 0) {
            int x = nextInt(), y = nextInt();
            if (x == y) {
                continue;
            }
            if (adjacencyMatrix[x][y] > INF / 2) {
                System.out.println(map.get(x) + "到" + map.get(y) + "不能直接到达");
            } else {
                System.out.println(map.get(x) + "到" + map.get(y) + "的最短距离为" + adjacencyMatrix[x][y] + "万公里");
            }
        }

    }

    static void showAllMinRoad() {
        //打印邻接矩阵
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    if (adjacencyMatrix[i][j] > INF / 2) {
                        System.out.println(map.get(i) + "到" + map.get(j) + "不能直接到达");
                    } else {
                        System.out.println(map.get(i) + "到" + map.get(j) + "的最短距离为" + adjacencyMatrix[i][j] + "万公里");
                    }
                }
            }
        }
    }

    static void floyd() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    adjacencyMatrix[i][j] = Math.min(adjacencyMatrix[i][j], adjacencyMatrix[i][k] + adjacencyMatrix[k][j]);
                }
            }
        }
    }

    static void showCity(){
        for (Map.Entry<Integer,String> entry: map.entrySet()){
            System.out.println(entry.getKey()+" "+entry.getValue());
        }
    }

    public static void main(String[] args) throws Exception {
        map.put(1, "太原");
        map.put(2, "北京");
        map.put(3, "上海");
        map.put(4, "深圳");
        map.put(5, "广州");
        map.put(6, "大同");
        while (isContinue) {
            System.out.println("------------------欢迎来到交通咨询系统-----------------");
            System.out.println("功能列表：");
            System.out.println("1.添加城市及其序号(系统中已经有6个城市)");
            System.out.println("2.输入城市之间的路径信息");
            System.out.println("3.查询某几个城市的最短路径信息");
            System.out.println("4.列出所有城市间的最短路信息");
            System.out.println("5.列出当前的所有城市");
            System.out.println("6.显示两个城市的直接可达距离");
            System.out.println("7.退出程序");
            System.out.println("请输入序号选择功能");
            choose = nextInt();
            switch (choose) {
                case 1:
                    addCity();
                    break;
                case 2:
                    inputModel();
                    break;
                case 3:
                    query();
                    break;
                case 4:
                    showAllMinRoad();
                    break;
                case 5:
                    showCity();
                    break;
                case 6:
                    showInput();
                    break;
                case 7:
                    isContinue = false;
                    break;
                default:
                    System.out.println("输入错误，请重新输入");
            }
        }

    }
}
